package leetcode.Hot100;

import collection.LinkedHashMapLRUStudy;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Cheng Jun
 * Description: 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
 * 实现 LRUCache 类：
 * <p>
 * LRUCache(int capacity) 以正整数作为容量capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 * 链接：https://leetcode-cn.com/problems/lru-cache
 * <p>
 * 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
 * 提示：双向链表，哈希表
 * @version 1.0
 * @date 2021/11/16 19:24
 * @see LinkedHashMapLRUStudy
 */
public class LRUCache1 {

    Map<Integer, DoubleLinkedNode> cacheMap;
    private int capacity;
    private DoubleLinkedNode head;
    private DoubleLinkedNode tail;

    public LRUCache1(int capacity) {
        this.capacity = capacity;
        cacheMap = new HashMap<>();
        head = new DoubleLinkedNode(Integer.MAX_VALUE, Integer.MAX_VALUE);
        tail = new DoubleLinkedNode(Integer.MIN_VALUE, Integer.MIN_VALUE);
        // 维护哑节点
        head.before = null;
        head.after = tail;
        tail.before = head;
        tail.after = null;
    }

    public static void main(String[] args) {
        // 双向链表的移除操作的时间复杂度是 O(n)
        LRUCache1 lruCache = new LRUCache1(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }

    public int get(int key) {
        if (cacheMap.containsKey(key)) {
            DoubleLinkedNode doubleLinkedNode = cacheMap.get(key);
            // 该节点插到 tail 前
            afterNodeAccess(doubleLinkedNode);
            return cacheMap.get(key).value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        // cacheMap 不存在该key
        if (!cacheMap.containsKey(key)) {
            // 未超过容量限制
            if (cacheMap.size() < capacity) {
                // 生成 DoubleLinkedNode，
                DoubleLinkedNode doubleLinkedNode = new DoubleLinkedNode(key, value);
                // 该节点插到 tail 前
                afterNodeAccess(doubleLinkedNode);
                cacheMap.put(key, doubleLinkedNode);
            } else { // 超过容量限制
                // 移除head.after
                DoubleLinkedNode first = head.after;
                head.after = first.after;
                first.after.before = head;
                cacheMap.remove(first.key);
                // 生成 DoubleLinkedNode，
                DoubleLinkedNode doubleLinkedNode = new DoubleLinkedNode(key, value);
                // 该节点插到 tail 前
                afterNodeAccess(doubleLinkedNode);
                cacheMap.put(key, doubleLinkedNode);
            }
        } else { // 已经存在
            DoubleLinkedNode doubleLinkedNode = cacheMap.get(key);
            // 该节点插到 tail 前
            afterNodeAccess(doubleLinkedNode);
            doubleLinkedNode.value = value;
        }
    }

    private void afterNodeAccess(DoubleLinkedNode node) {
        // 如果该节点就是 tail的前驱 就不做处理
        if (tail.before == node) {
            return;
        }
        // 如果cacheMap 中有该节点，就先调整该节点的 前驱节点的后驱，后驱节点的前驱
        if (cacheMap.containsKey(node.key)) {
            node.before.after = node.after;
            node.after.before = node.before;
        }
        DoubleLinkedNode before = tail.before;
        before.after = node;
        node.before = before;
        tail.before = node;
        node.after = tail;
    }

    class DoubleLinkedNode {
        DoubleLinkedNode before;
        DoubleLinkedNode after;
        Integer key;
        Integer value;

        public DoubleLinkedNode(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }
}
